An exact algorithm for the weighed mutually exclusive maximum set cover problem

摘要

In this paper, we introduce an exact algorithm with a time complexity of$O^*(1.325^m)$ for the {\sc weighted mutually exclusive maximum set cover}problem, where $m$ is the number of subsets in the problem. This is an NP-hardmotivated and abstracted from a bioinformatics problem of identifying signalingpathways based gene mutations. Currently, this problem is addressed usingheuristic algorithms, which cannot guarantee the performance of the solution.By providing a relatively efficient exact algorithm, our approach will likeincrease the capability of finding better solutions in the application ofcancer research.